//组合总和三 力扣216
//回溯法
//缺点：sum是最后进行遍历计算的，可能会导致时间复杂度较高
class Solution {
private:
	vector<int> path;
	vector<vector<int>> ans;
	void backtracking(int k,int n, int startindex)
	{
		if(path.size() == k)
		{
			int sum = 0;
			for(int i = 0; i < path.size(); i++)
				sum += path[i];
			if(sum == n) ans.push_back(path);
			return;  
		}
		for(int i = startindex; i <= 9-(k-path.size())+1; i++)
		{
			path.push_back(i);
			backtracking(k,n,i+1);
			path.pop_back();
		}
	} 
public:
	vector<vector<int>> combinationSum3(int k, int n) {
		backtracking(k,n,1);
		return ans;
	}
};
